In this article we give an algorithm for the computation of the number ofrational points on the Jacobian variety of a generic ordinary hyperellipticcurve defined over a finite field of cardinality $q$ with time complexity$O(n^{2+o(1)})$ and space complexity $O(n^2)$, where $n=\log(q)$. In the lattercomplexity estimate the genus and the characteristic are assumed as fixed. Ouralgorithm forms a generalization of both, the AGM algorithm of J.-F. Mestre andthe canonical lifting method of T. Satoh. We canonically lift a certainarithmetic invariant of the Jacobian of the hyperelliptic curve in terms oftheta constants. The theta null values are computed with respect to asemi-canonical theta structure of level $2^\nu p$ where $\nu >0$ is an integerand $p=\mathrm{char}(\F_q)>2$. The results of this paper suggest a globalpositive answer to the question whether there exists a quasi-quadratic timealgorithm for the computation of the number of rational points on a genericordinary abelian variety defined over a finite field.
展开▼
机译：在本文中，我们给出了一种算法，用于计算在基数为$ q $的有限字段上定义的通用普通超椭圆曲线的Jacobian阶上的时间上的复杂度$ O（n ^ {2 + o（1）} ）$和空间复杂度$ O（n ^ 2）$，其中$ n = \ log（q）$。在后一种复杂性估计中，将属和特性假定为固定的。我们的算法构成了J.-F.的AGM算法的综合。麦斯特（Mestre）和T. Satoh的规范提升方法。根据θ常数，我们典型地提升了超椭圆曲线的雅可比定律。相对于级别$ 2 ^ \ nu p $的半经典theta结构计算theta零值，其中$ \ nu> 0 $是整数，$ p = \ mathrm {char}（\ F_q）> 2 $。本文的结果提出了一个全局肯定的答案，即对于在有限域上定义的一般阿贝尔变种上的有理点数的计算是否存在准二次时间算法。
展开▼
